package problems.solved;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import problems.Problem;

import utils.Utils;

public class Problem87 extends Problem<Integer> {
	private static final int TARGET = 50000000;

	private static final List<Integer> primes = Utils.sieve(8000);

	public static void main(String[] args) {
		Problem87 problem87 = new Problem87();
		problem87.runTimed();
		problem87.printResult();
	}

	@Override
	public void run() {
		List<Long> aList = new ArrayList<Long>();
		List<Long> bList = new ArrayList<Long>();
		List<Long> cList = new ArrayList<Long>();
		
		for (long prime : primes) {
			long n = prime*prime;
			if (n > TARGET) {
				break;
			}
			aList.add(n);
			n *= prime;
			if (n < TARGET) {
				bList.add(n);

				n *= prime;
				if (n < TARGET) {
					cList.add(n);
				}
			}
		}
		
		Set<Long> set = new HashSet<Long>();
		for (long a : aList) {
			for (long b : bList) {
				for (long c : cList) {
					final long n = a + b + c;
					if (n < TARGET) {
						set.add(n);
					}
				}
			}
		}
		setResult(set.size()); //1097343
	}
}
